Bài toán P so với NP

Lớp độ phức tạp P thường được xem là mô hình toán học cho các vấn đề tính toán có thuật toán hiệu quả. Giả thuyết này được gọi là luận đề Cobham-Edmonds. Trong khi đó lớp độ phức tạp NP chứa nhiều bài toán quan trọng cần được giải quyết hiệu quả, nhưng vẫn chưa có thuật toán hiệu quả nào, chẳng hạn như bài toán thỏa mãn biểu thức logic, bài toán đường đi Hamilton, và bài toán phủ đỉnh. Do máy Turing đơn định là trường hợp đặc biệt của máy Turing không đơn định, có thể dễ dàng nhận thấy mọi bài toán trong P đều nằm trong NP.

Câu hỏi liệu P có bằng NP hay không là một trong những câu hỏi quan trọng nhất trong lý thuyết khoa học máy tính do tính áp dụng rộng rãi của lời giải.[2] Nếu câu trả lời là có, thì nhiều bài toán quan trọng có thể được giải quyết hiệu quả. Những bài toán này bao gồm nhiều loại quy hoạch nguyên trong vận trù học, nhiều vấn đề trong hậu cần, dự đoán cấu trúc protein trong sinh học,[3] và khả năm tìm chứng minh chặt chẽ cho các định lý toán học.[4] Bài toán P so với NP là một trong những bài toán giải thưởng thiên niên kỷ lựa chọn bởi Viện Toán học Clay. Có một giải thưởng US$1.000.000 cho việc giải quyết bài toán.[5]

Bài toán trong NP không nằm trong P và không là NP-đầy đủ

Ladner đã chứng minh rằng nếu P ≠ NP thì tồn tại bài toán trong NP không nằm trong P cũng như không là NP-đầy đủ.[6] Các bài toán như vậy gọi là bài toán NP-trung bình. Bài toán đồ thị đẳng cấu, bài toán tính lôga rời rạc, và bài toán phân tích ra thừa số nguyên tố là các ví dụ của những bài toán được tin là NP-trung bình. Chúng nằm trong số rất ít bài toán trong NP không biết có nằm trong P và cũng không biết có là NP-đầy đủ.

Phân biệt giữa các lớp độ phức tạp khác

Có nhiều lớp độ phức tạp được tin là khác nhau những vẫn chưa được chứng minh. Ví dụ như P ⊆ NP ⊆ PP ⊆ PSPACE và hoàn toàn có thể P=PSPACE. Nếu P không bằng NP thì P không bằng PSPACE. Do có rất nhiều lớp độ phức tạp giữa P và PSPACE, chẳng hạn như RP, BPP, PP, BQP, MA, PH, v.v., hoàn toàn có thể là tất cả các lớp này đều bằng nhau. Chứng minh bất kì hai lớp nào trong số đó là khác nhau sẽ là một bước tiến lớn trong lý thuyết độ phức tạp.

Tương tự như vậy, co-NP là lớp chứa các bài toán phần bù (các bài toán với câu trả lời có/không đảo ngược) của các bài toán trong NP. Người ta tin rằng [7] NP không bằng co-NP, nhưng điều này vẫn chưa được chứng minh. Nếu hai lớp này không bằng nhau thì P cũng không bằng NP.

Tương tự như vậy, vẫn chưa biết liệu L (tập hợp các bài toán giải được trong bộ nhớ lôgarit) có bằng P hay không. Có nhiều lớp độ phức tạp nằm giữa hai lớp, chẳng hạn như NL và NC, và vẫn chưa biết liệu chúng bằng nhau hay khác nhau.

P và BPP có nhiều khả năng là bằng nhau. Tuy nhiên hiện vẫn chưa biết liệu BPP có bằng NEXP.